|
In graph theory, a factor of a graph ''G'' is a spanning subgraph, i.e., a subgraph that has the same vertex set as ''G''. A ''k''-factor of a graph is a spanning ''k''-regular subgraph, and a ''k''-factorization partitions the edges of the graph into disjoint ''k''-factors. A graph ''G'' is said to be ''k''-factorable if it admits a ''k''-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of a ''k''-regular graph is an edge coloring with ''k'' colors. A 2-factor is a collection of cycles that spans all vertices of the graph. ==1-factorization== If a graph is 1-factorable, then it has to be a regular graph. However, not all regular graphs are 1-factorable. A ''k''-regular graph is 1-factorable if it has chromatic index ''k''; examples of such graphs include: * Any regular bipartite graph.〔, Theorem 9.2, p. 85. , Corollary 2.1.3, p. 37.〕 Hall's marriage theorem can be used to show that a ''k''-regular bipartite graph contains a perfect matching. One can then remove the perfect matching to obtain a (''k'' − 1)-regular bipartite graph, and apply the same reasoning repeatedly. * Any complete graph with an even number of nodes (see below).〔, Theorem 9.1, p. 85.〕 However, there are also ''k''-regular graphs that have chromatic index ''k'' + 1, and these graphs are not 1-factorable; examples of such graphs include: * Any regular graph with an odd number of nodes. * The Petersen graph. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「graph factorization」の詳細全文を読む スポンサード リンク
|